perm filename CMPARE[0,BGB] blob sn#116864 filedate 1974-08-30 generic text, type C, neo UTF8
COMMENT ⊗   VALID 00006 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	{F1F2F3F4⊂C<NαCOMPARING.λ30P95I425,0JCFA} SECTION 8.
C00008 00003	⊂8.1 	A Polygon Matching Method.⊃
C00015 00004	⊂8.2	Geometric Normalization of Polygons.⊃
C00019 00005	⊂8.3	Compare by Recursive Windowing.⊃
C00021 00006	⊂8.4	Related Work and Work Yet To Be Done.⊃
C00023 ENDMK
C⊗;
{F1;F2;F3;F4;⊂C;<N;αCOMPARING.;λ30;P95;I425,0;JCFA} SECTION 8.
{JCFD}    IMAGE COMPARING.
{λ10;W250;JAFA}
	8.0	Introduction to Image Comparing.
	8.1 	A Polygon Matching Method.
	8.2	Geometric Normalization of Polygons.
	8.3	Compare by Recursive Windowing.
	8.4	Related Work and Work Yet To Be Done.
{λ30;W0;I950,0;JU;FA}
⊂8.0	Introduction to Image Comparing.⊃

	The  image compare  process  is both  the  <"keystone of  the
arch">  as well as  the <"weakest link  of the  chain">. By comparing
images, the 3-D  modeling and  the 2-D image  processing are  finally
linked,   however  as will  be  apparent the  implementation to  date
demonstrates  only a small part of what  is possible. In the feedback
perception design,   there are three  classes of compare  operations:
verification,   revelation and  recognition which  may be  applied to
each of the three kinds of image data structures: raster, contour and
mosaic.  The verify compare finds  the corresponding entities between
a predicted  image and a perceived image  for the sake of calibration
measurement and  for the sake  of eliminating  already known  features
from  further   consideration.  In  vision  for   industrial  machine
assembly, calibration  measurements suddenly seems to be the only kind
of vision necessary in a relatively constrained
factory  situation. The reveal  compare
involves finding the  corresponding entities in two perceived images,
so that  the  location and  extent  of  new objects  can  be  solved.
Finally,   the  recognition  compare  involves matching  a  perceived
entity with one of a set of prototype entities.

	From the  view  point of  modeling the  lowest level  compare
operation  should somehow  be arranged  to be a  one to  one template
match rather than a multi dimensional statistical discrimination or a
graph isomorphism  test. That is  if the  entities to be  matched are
incommensurate,  the model designer censures the model that generated
an  unrealistic prediction  rather  than  the pattern  matcher  which
cannot see  a vague resemblance. Clearly this  position should not be
taken to an extreme and the  present system could be enhanced by  the
inclusion  of  an  appropriate  collection   of  traditional  pattern
matching techniques.  However,  two techniques of commensuration that
are naturally  the responsibility of  a model  builder are  geometric
normalization and topological  segmentation.  Geometric normalization
involves  eliminating  the irrelevant  geometric differences such  as location,
orientation and scale.  Topological segmentation involves subdividing
a  complex object into  pieces,   (perhaps even canonical  pieces) so
that only simple  small parts need  be matched (that  is the  compare
becomes recursive).  The remainder of this  chapter explains a method
for  matching  structured  images consisting  of  polygons.  The most
original part  of  the method  involves finding  the  correspondence,
illustrated in  Figure 8.1,   for polygonal  figures that  fission or
fuse from one image to the next.
{I∂12,0;JCFC} FIGURE 8.1  -  EXAMPLE OF POLYGON FUSION COMPARE.
{X.615;H2;I∂-120,15;⊗CMPAR1.PLT;I∂0,615;⊗CMPAR2.PLT;
X0.95;I∂715,630;*CMPAR4.PLT;JUFAQ}
⊂8.1 	A Polygon Matching Method.⊃

	The image compare  process in CRE, connects the  polygons and
vectors of one image  with corresponding  polygons and vectors of another
image. CRE's  compare  solves  the problem  of  correlating  polygons
between two similar images and is composed of four steps: 
{λ10;JA}
   1. Compute polygonal lamina inertia tensors, <lamten nodes>.
   2. Compare and connect polygons one to one at corresponding levels of the nested polygon tree.
   3. Compare and connect polygons two to one at corresponding levels of the nested polygon tree.
   4. Compare and connect vertices of connected polygons using recursive windowing.
{λ30;JU}
	First, the lamina inertia tensor nodes (called <lamten>'s) of
all the  polygons of an image are  computed. A lamten node contains
the center of mass as well as the tensor of a polygon. The meaning
of the  inertia tensor  is that  it characterizes  each polygon  as a
rectangle of  a certain length and width at a particular location and
orientation; and  of further  importance  such inertia  tensors can  be
added to characterize two or more polygons by a single rectangle.  It
is the lamten rectangles that provide a basis for normalization.

	Second, all the lamtens  of the polygons of one  level of the
first image are  compared with all the lamtens of the polygons of the
corresponding level of the second image for nearly exact match.   The
potentially (M*N/2) compares  is avoided by sorting on  the center of
mass  locations.  In CRE,  which  is intended for comparing sequences
of pictures of natural scenes;  match for center of mass  location is
tested  first and  most  strictly,   followed by  match  for inertia.
Pointers between matching polygons are  placed in two link  positions
of the polygon nodes  and the polygons are considered to  be matched.

	Third,  all  the unmated polygons  of a level  are considered
two at  a time and a fusion  lamten node for each pair  is made.  The
potentially (N*N/2-N) fusion lamtens  are avoided because there is  a
maximum possible unmated inertia in the  other image; if there are no
unmated  polygons in one image  then the extra  polygons of the first
image can be ignored. In  the event where there are  unmated polygons
in corresponding  levels of the two images,  the multi-polygon fusion
lamten of one  are compared  with the  single polygon  lamten of  the
other. The fusion (fission) compare solves  the rather nasty problem,
of  linking two contour polygons  of one image with  a single contour
polygon in the next image.

	Fourth, the vertices  of mated polygons are in  turn compared
and mated.   To start a vertex compare,   the vertices of one polygon
are translated,   rotated and  dilated to get  that polygon's  lamten
rectangle coincident  with its mate  (or mates).   Conceptually, each
vertex  of one  polygon  is compared  with each  vertex of  the other
polygon(s) and the mutually closest vertices (closer than an epsilon)
are considered  to be mated.   Actually the  potential (N*M) compares
are avoided by a recursive windowing  scheme similar to that used  in
hidden line elimination algorithms. The  compare execution takes less
than a  second on images such as the pump  base (Figures 0.3 and 0.4)
blocks (Figure 8.1) and a doll (Figure 8.2). The doll's silhouette is
headless when viewed from the backside because its hair is black.

{FCJC} FIGURE 8.2  -  EXAMPLE OF VERTEX MATCHING.
{X0.95;I∂220,630;H2;*CMPAR3.PLT;I∂400,0;JUFA}
⊂8.2	Geometric Normalization of Polygons.⊃

	The  lamina inertia  tensor  of a  polygon  with N  sides  is
computed by summation over N trapezoids.  The trapezoid corresponding
to each side is formed by dropping perpendiculars <up> to the  top of
the image  frame; each such  trapezoid consists  of a rectangle  an a
right triangle;  since the sides of polygons are directed vectors the
areas  of the  triangles  and  rectangles  can be  arranged  to  take
positive and negative values  such that a summation will describe the
interior region of the polygon as positive.  The equations  necessary
for computing  the lamina inertia  tensor of  a polygon were  derived
from material in (Goldstein 1950).
{λ8;JA}
RECTANGLE'S  LAMINA INERTIA TENSOR ABOUT ITS CENTER OF MASS.
	MXX	←	B*B*AREA/12;		(B HEIGHT IN ROWS).
	MYY 	←	A*A*AREA/12;		(A WIDTH IN COLUMNS).
	MZZ	←	MXX + MYY;
	PXY 	←	0;

ORIENTED RIGHT TRIANGLE'S LAMINA INERTIA TENSOR ABOUT ITS CENTER OF MASS.
	MXX	←	B*B*AREA/18;		(B HEIGHT IN ROWS).
	MYY	←	A*A*AREA/18;		(A WIDTH IN COLUMNS).
	MZZ	←	MXX + MYY;
	PXY	←	-A*B*AREA/36;

SUMMATION OF LAMINA INERTIA TENSORS.
	AREA	←	(AREA1  +  AREA2);
	XCM	←	(AREA1 * XCM1  +  AREA2 * XCM2) / AREA;
	YCM	←	(AREA1 * YCM1  +  AREA2 * YCM2) / AREA;
	MXX	←	MXX1 +YCM1*YCM1*AREA1 +MXX2 +YCM2*YCM2*AREA2  -YCM*YCM*AREA;
	MYY	←	MYY1 +XCM1*XCM1*AREA1 +MYY2 +XCM2*XCM2*AREA2  -XCM*XCM*AREA;
	PXY	←	PXY1 -XCM1*YCM1*AREA1 +PXY2 -XCM2*YCM2*AREA2  +XCM*YCM*AREA;

ANGLE OF PRINCIPLE AXIS
The angle of the principle axis, PHI, lies in the interval -π/2 to π/2.
	PHI	←	0.5*ATAN(2*PXY/(MYY-MXX));
	PXY	←	0.5*(MYY - MXX)*TAN(2*PHI);

TRANSLATION OF LAMINA INERTIA TENSOR AWAY FROM CENTER OF MASS.
	MXX'	←	MXX  +  AREA*DY*DY;
	MYY'	←	MYY  +  AREA*DX*DX;
	PXY'	←	PXY  -  AREA*DX*DY;

ROTATION OF LAMINA INERTIA TENSOR ABOUT CENTER OF MASS.
	C	←	COSINE(PHI);
	S	←	SINE(PHI);
	MXX'	←	C*C*MXX  +  S*S*MYY  -  2*C*S*PXY;
	MYY'	←	C*C*MYY  +  S*S*MXX  +  2*C*S*PXY;
	PXY'	←	(C*C - S*S)*PXY + C*S*(MYY - MXX);
{λ30;JUQ}

⊂8.3	Compare by Recursive Windowing.⊃

	The final step in  the CRE polygon match (Section  8.1) is
to   link  the  corresponding  vertices   between  two  geometrically
normalized polygons (or  sets of polygons)  using a nearest  neighbor
criterion. The  nearest neighbors  are found by  recursive windowing,
initially  all the vertices are pushed into  one large window which is
subsequently split until there  were few enough vertices  contained in
the  window to  allow exhaustive  comparing.   To make  this windowing
technique applicable  to  the  nearest neighbor  problem  a  distance
criterion, <delta>, has to be declared so that the windows overlap by
that  amount.    Consequently  the  windows  are no  longer  disjoint
rectangles, but are rather boxes with rounded corners,   the smallest
possible window being  a circle with radius, <delta>.   The recursive
windowing  technique is essentially a two dimensional partition sort,
the  technique can  be  generalized  for comparing  edges  and  other
entities in 2-D or higher dimensions.

⊂8.4	Related Work and Work Yet To Be Done.⊃

	To complete the visual feedback system,  there remains yet to
be written an image  compare that uses both raster based and polygon based
techniques. The  two kinds  of  compares are  symbiotic in  that  the
polygon compare could aim the  raster correlator alleviating the need
to  do bulk  correlation over wide  areas, and  the raster correlator
could verify  and  improve the  measurement  of corresponding  vertex
loci.  At Stanford, image comparison by raster correlation techniques
is begin worked on by Quam(71),  Hannah and Morevac.  Another  approach
to comparing polygons is to examine their curvature, the curvature of
a  polygon can be expressed  as a parametric function  of arc length;
two such  functions can be  normalized and  alligned and  differenced
using statistical techniques (Zahn 66).